"""
    python实现单链表
"""


class ListNode:
    """节点类: 节点超级工厂,用来生产节点"""
    def __init__(self, val):
        self.val = val
        self.next = None


class LinkList:
    def __init__(self):
        """
        初始化一个空链表:头节点为None的链表为空链表
        """
        self.head = None

    def is_empty(self):
        """
        判断是否为空链表
        :return: True | False
        """
        return self.head == None

    def append(self, item):
        """
        在链表尾部添加一个节点
        """
        node = ListNode(item)
        # 1.空链表情况
        if not self.head:
            self.head = node
        else:
            cur = self.head
            # 非空链表情况
            while cur.next:
                cur = cur.next

            # 循环结束,cur指向尾节点
            cur.next = node
            node.next = None

    def travel(self):
        """
        从头到尾遍历链表
        """
        if not self.head:
            return

        cur = self.head
        while cur:
            print(cur.val, end=" ")
            cur = cur.next

        print()

    def remove(self, item):
        """
        移除链表中的一个节点
        :param item: 数据区
        :return: None  节点不存在则抛出异常
        """
        # 1.空链表情况
        if not self.head:
            raise Exception("x not in LinkList")

        # 2.删除头节点情况
        if self.head.val == item:
            self.head = self.head.next
            return

        # 3.非头节点情况
        pre = None
        cur = self.head
        while cur:
            if cur.val != item:
                pre = cur
                cur = cur.next
            else:
                pre.next = cur.next
                return

        # 4.删除的节点不存在的情况
        raise Exception("x not in LinkList")

    def get_length(self):
        """
        获取链表长度
        :return: length
        """
        count = 0
        cur = self.head
        while cur:
            count += 1
            cur = cur.next

        return count

    def insert(self, index, item):
        """
        在指定索引值位置插入一个节点
        :param index: 索引值
        :param item: 数据区
        :return: None  |  抛出异常(index<0)
        """
        if index < 0:
            raise Exception("index error")

        node = ListNode(item)
        # 头节点处插入情况 index=0
        if index == 0:
            node.next = self.head
            self.head = node
            return

        # index超出链表长度情况
        length = self.get_length()
        print(length)
        if index > (length - 1):
            self.append(item)
            return

        cur = self.head
        for i in range(index - 1):
            cur = cur.next

        node.next = cur.next
        cur.next = node

    def pop(self):
        """
        在链表尾部弹出一个节点
        :return: 尾节点的数据
        """
        length = self.get_length()
        # 1.空链表
        if length == 0:
            raise Exception("pop from empty linklist")

        # 2.只有头节点情况
        if length == 1:
            item = self.head.val
            self.head = None

            return item

        # 3.链表中有2个及以上节点的情况
        cur = self.head
        while cur.next.next:
            cur = cur.next

        item = cur.next.val
        cur.next = cur.next.next

        return item


if __name__ == '__main__':
    ls = LinkList()
    # 终端1: True
    print(ls.is_empty())
    # 链表: 100 -> 200 -> 300 -> None
    ls.append(100)
    ls.append(200)
    ls.append(300)

    # 终端2: 100 200 300
    ls.travel()

    print(ls.pop())
    print(ls.pop())
    print(ls.pop())

    # # 终端3: False
    # print(ls.is_empty())
    # # 原来:  100 200 300
    # # 终端4: 100 300
    # ls.remove(200)
    # ls.travel()
    # # 链表: 100 300 400 500
    # ls.append(400)
    # ls.append(500)
    # # 终端5: 100 666 300 400 500
    # ls.insert(1, 666)
    # ls.travel()
































